package A_sort;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class CheckAlgorithm {


    /**
     * java自带数组排序
     */
    public static void sort(int[] arr) {
        Arrays.sort(arr);
    }

    /**
     * 生成随机数组
     *
     * @param maxLength
     * @param maxValue
     * @return
     */
    public static int[] genArr(int maxLength, int maxValue) {
        int[] arr = new int[(int) ((maxLength + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
        }
        return arr;
    }

    /**
     * 生成只有一个数字出现了奇数次的数组
     */
    public static int[] genOneOddArr(int maxLength, int maxValue) {
        int[] arr = new int[((int) ((maxLength / 2) * Math.random()) + 1) * 2 - 1];
        int length = arr.length;
        for (int i = 0; i < length; i++) {
            arr[i] = -1;
        }
        int i = 0;
        while (i < length) {
            int j = 0 ;
            int value = (int) ((maxValue + 1) * Math.random());
            if (i == 0) {
                int oddNum = ((int)(length*Math.random()))/2*2-1;
                if (oddNum <= 0) {
                    oddNum = 1;
                }
                while (j < oddNum) {
                    int randomIndex = (int) ((length) * Math.random());
                    while (arr[randomIndex] != -1) {
                        randomIndex = (int) ((length) * Math.random());
                        continue;
                    }
                    arr[randomIndex] = value;
                    j++;
                    i++;
                }
            } else {
                int evenNum = ((int)(length*Math.random()))/2*2;
                if (evenNum<2){
                    evenNum = 2;
                }
                while (j < evenNum) {
                    int randomIndex = (int) ((length) * Math.random());
                    int count = 0;
                    for (int k = 0; k < arr.length; k++) {
                        if (arr[k]==-1){
                            count++;
                        }
                    }
                    if (count==0){
                        break;
                    }
                    while (arr[randomIndex] != -1&&count>0) {
                        randomIndex = (int) ((length) * Math.random());
                        continue;
                    }
                    arr[randomIndex] = value;
                    i++;
                    j++;
                }
            }
        }
        return arr;
    }



    /**
     * 找出现了奇数次的数字
     */
    public static int findOddNumber1Check(int[] arr){
        Map<Integer,Integer> map = new HashMap<Integer,Integer>();
        for (int i = 0; i < arr.length; i++) {
            if (map.containsKey(arr[i])){
                map.put(arr[i],map.get(arr[i])+1);
            }else {
                map.put(arr[i],1);
            }
        }
        for (Map.Entry<Integer,Integer> e:map.entrySet()){
            if (e.getValue()%2==1){
                return e.getKey();
            }
        }
        return -1;
    }

    /**
     * 复制数组
     *
     * @param arr
     * @return
     */
    public static int[] copyArr(int[] arr) {
        if (arr == null) {
            return null;
        }
        int[] copy = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            copy[i] = arr[i];
        }
        return copy;
    }

    /**
     * 比较结果
     *
     * @param testArr
     * @param compareArr
     * @return
     */
    public static boolean compareArr(int[] testArr, int[] compareArr) {
        boolean flag = true;
        for (int i = 0; i < testArr.length; i++) {
            if (testArr[i] != compareArr[i]) {
                flag = false;
            }
        }
        return flag;
    }

    public static void main(String[] args) {
        int times = 100000;
        int maxLength = 1000;
        int maxValue = 1000;
        //检验排序是否正确
//        for (int i = 0; i < times; i++) {
//            int[] testArr = genArr(maxLength,maxValue);
//            int[] compareArr = copyArr(testArr);
//            A_SelectSort.selectSort(testArr);
//            sort(compareArr);
//            if (!compareArr(testArr,compareArr)){
//                System.out.println("failed");
//                break;
//            }
//        }




        for (int i = 0; i < times; i++) {
            int[] testArr = genOneOddArr(maxLength, maxValue);
            int[] compareArr = copyArr(testArr);
            if (findOddNumber1Check(compareArr)!=Questions.findOddNumber1(testArr)) {
                System.out.println("第"+i+"失败");
                System.out.println("数组长度"+testArr.length);
                System.out.println(Arrays.toString(testArr));
                System.out.println("返回结果"+findOddNumber1Check(compareArr));
                System.out.println("期望结果"+Questions.findOddNumber1(testArr));
                System.out.println("failed");
                break;
            }
        }
            System.out.println("success");


    }
}
